/**
 * 
 */
package datastructure;

import java.util.Collection;
import java.util.Iterator;
import java.util.Queue;
import java.util.LinkedList;

/**
 * Using 2 queue. queue for data, and minQueue for putting min values
 * 
 * add: polls all elements which are larger than input element and then adds it into min Queue.
 * adds the insert element into queue
 * remove: if queue.peek == minQueue.peek, remove minqueue and return queue.remove
 * getMin: return the first element in the minqueue
 * 
 * 
 * C++ code
 * class DataStructure {
 protected:
 deque<int> q;
 deque<int> v;
 public:
 void push_back(int data)
 {
 while (v.size()>0) {
 if (v.back()>data) v.pop_back();
 else break;
 }
 q.push_back(data);
 v.push_back(data);
 }
 int pop_front() {
 int ret = q.pop_front();
 if (ret==v.front()) v.pop_front();
 return ret;
 }
 int size() {
 return q.size();
 }
 int minValue() {
 assert(v.size()>0);
 return v.front();
 }
 }
 */



/**
 * @author Michael
 *
 */
public class MinQueue<E extends Comparable<? super E>> {

	
	Queue<E> minQueue = null;
	Queue<E> queue = null;
	
	/**
	 * 
	 */
	public MinQueue() {
		queue = new LinkedList<E>();
		minQueue = new LinkedList<E>();
	}



	public void clear() {
		queue.clear();
		minQueue.clear();
	}



	public boolean isEmpty() {
		return queue.isEmpty();
	}



	public int size() {
		return queue.size();
	}


	public Object[] toArray() {
		return queue.toArray();
	}


	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] array) {
		return (T[]) queue.toArray(array);
	}


	public boolean add(E e) {
		if (e == null) return false;
		
		while (!queue.isEmpty()) {
			if (minQueue.peek().compareTo(e) > 0) {
				minQueue.poll();
			}
			queue.add(e);
			minQueue.add(e);
		}
		return true;
	}

	public E getMin() {
		return minQueue.peek();
	}
	
	public boolean offer(E e) {
		return add(e);
	}


	public E remove() {
		if (queue.peek().compareTo(minQueue.peek()) == 0) {
			minQueue.remove();
			
		}
		return queue.remove();
	}


	public E poll() {
		// TODO Auto-generated method stub
		return null;
	}


	public E element() {
		// TODO Auto-generated method stub
		return null;
	}


	public E peek() {
		return queue.peek();
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
